package com.example.hot100;

/**
 * 给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
 *  给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。
 *  完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
 *
 *  示例 1：
 * 输入：n = 12
 * 输出：3
 * 解释：12 = 4 + 4 + 4
 *
 *  示例 2：
 * 输入：n = 13
 * 输出：2
 * 解释：13 = 4 + 9
 */
public class Leetcode279_NumSquares {
    public static void main(String[] args) {
        System.out.println(new Solution().numSquares(12));
    }

    static class Solution {
        /**
         * 四平方和定理:任意一个正整数都可以被表示为至多四个正整数的平方和
         * 另外当 n = 4^k * (8m + 7) 时，n 只能被表示为四个正整数的平方和
         * @param n
         * @return
         */
        private int numSquares2(int n) {
            if (isPerfectSquare(n)) {
                return 1; // 平方根为整数,返回 1
            } else {
                for (int i = 1; i * i < n; i++) {
                    if (isPerfectSquare(n - i *i )) return 2;
                }

                if (checkAnswer4(n)) return 4; // 判断是否能表示为 4^k*(8m+7)

                return 3;// 都不满足则返回3
            }
        }

        // 判断是否为完全平方数
        private boolean isPerfectSquare(int x) {
            int y = (int) Math.sqrt(x);
            return y * y == x;
        }


        private boolean checkAnswer4(int x) {
            while (x % 4 == 0) {
                x /= 4;
            }
            return x % 8 == 7;
        }

        /**
         * 动态规划
         * @param n
         * @return
         */
        private int numSquares1(int n) {
            int[] dp = new int[n + 1]; // dp[i]表示最少需要多少个数的平方来表示整数 i。

            for (int i = 1; i <= n; i++) { // 从 1 ~ n 依次计算每个数所需要的最少需要多少个数的平方来表示
                int count = Integer.MAX_VALUE;
                for (int j = 1; j * j <= i; j++) { //  从 1 ~ sqrt(i) 枚举每一个j 使得 i = j^2 + (i - j^2), 而 (i - j^2)前面已经计算过了,因此只需要查表即可
                    count = Math.min(count, dp[i - j * j]);
                }

                dp[i] = count + 1;  // i = j^2 + (i - j^2) 分成两部分看即 (i - j^2) 所需的最小个数值 + j^2 (1个)
            }

            return dp[n];
        }

        public int numSquares(int n) {
            return numSquares2(n);
        }
    }
}
